"""
https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

4. 寻找两个正序数组的中位数
已解答
困难
相关标签
相关企业
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

 

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 

 

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

"""

from typing import List


class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        """
        如果m+n是奇数，则相当于找第(m+n+1)/2小的数
        如果m+n是偶数，则相当于找第(m+m)/2小的数，和第(m+n)/2+1小的数，并取其平均值

        假定满足要求的索引，在nums1中是第x个，在nums2中是第y个。
        则满足以下两点要求：
        1. x+y=(len(nums1)+len(nums2))//2
        2. max(nums1[x],numx2[y])<=min(nums1[x+1],nums2[y+1])
        注：右侧的nums[x+1]和nums[y+1]如果不存在，则忽略。且只要len(nums1)+len(nums2)>0,则至少有一个不为空。

        换言之，要求就是找到这样的x和y。
        如果某一次找到的x和y满足要求1，但不满足要求2，则比较nums1[x]和nums2[y]哪个更大。
        如果nums1[x]<nums2[y],则x向上找更大的值，y同理向下找。
        反之，则x向下找，y向上找。
        不可能存在nums1[x]==nums2[y]且不满足要求2的情况（因为nums1[x]<nums1[x+1]且nums2[y]<nums2[y+1]）
        
        """

        total_count=len(nums1)+len(nums2)
        req_count=total_count//2

        if len(nums2)==0:
            left_count=(len(nums1)-1)//2
            return nums1[left_count] if len(nums1)%2==1 else (nums1[left_count]+nums1[left_count+1])/2
        if len(nums1)==0:
            left_count=(len(nums2)-1)//2
            return nums2[left_count] if len(nums2)%2==1 else (nums2[left_count]+nums2[left_count+1])/2

        def find_num(nums:List[int],i:int)->int:
            if 0<=i<len(nums):
                return nums[i]
            else:
                return None
            
        def find_compare(num1:int,num2:int,comp:str)->int:
            if num1 is not None and num2 is not None:
                if comp=='max':
                    return max(num1,num2)
                else:
                    return min(num1,num2)
            elif num1 is not None:
                return num1
            elif num2 is not None:
                return num2
            else:
                return None

        def compare_x(x:int)->List[int]:
            y=req_count-(x+1)-1
            left1=find_num(nums1,x)
            left2=find_num(nums2,y)
            left_max=find_compare(left1,left2,'max')
            
            right1=find_num(nums1,x+1)
            right2=find_num(nums2,y+1)
            right_min=find_compare(right1,right2,'min')

            # right_min必定不为None。left_max如果total_count<2,可能为None。原来的上下文需要自行处理这些情况。
            if left_max<=right_min:
                res=right_min if total_count%2==1 else (left_max+right_min)/2
                return [0,res]
            else:
                return [1,None] if (left2 is None or left1>left2) else [-1,None]
        

        # 将x从0到len(nums1)-1之间，进行二分查找
        # 这里的left1和right1，分别表示在左侧left1个元素，和左侧right1个元素之间，即从(数学意义上的)第left1+1到right1个元素之间，寻找符合要求的元素
        # 对应的数组索引，是[left1,right1-1]
        # x在这里表示的是替代的元素位置，-1表示左侧没有元素，0表示左侧有1个元素，以此类推
        left1=0
        right1=len(nums1)
        while left1<=right1:
            # 现在的问题是，x没有办法抵达0这个点
            left_count1=(left1+1+right1)//2
            [c,res]=compare_x(left_count1-1)
            if c==0:
                return res
            elif c==1:
                right1=left_count1-1
            else:
                left1=left_count1


        pass

if __name__=='__main__':
    # TODO 4. 寻找两个正序数组的中位数
    # 测试代码
    solution=Solution()
    nums1 = [2,3,4,5,6]
    nums2 = [1]
    res=solution.findMedianSortedArrays(nums1,nums2)
    print(res)